// Permutation.cs
// 
// This class is responsible for dealing with permutation algorithms 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;

namespace Mono.Algorithm
{
	/// <summary>
	/// Exception thrown for error produced whilst producing lexicographical permutations
	/// </summary>
	public class PermutationException : Exception
	{
		public PermutationException() : base() { }
		public PermutationException(string msg) : base(msg) { }
		public PermutationException(SerializationInfo info, StreamingContext sc) : base(info, sc) { }
		public PermutationException(string msg, Exception e) : base(msg, e) { }
	}
	
	public partial class Algorithm
	{
		/// <summary>
		/// Produces the next lexicographical permutation of a sequence
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="seq">The sequence to produce the next permutation from</param>
		/// <param name="start">The starting index to produce the permutation from</param>
		/// <param name="end">The last index of the sequence to produce the permutation to</param>
		public static bool NextPermutation<T>(ref List<T> seq, int start, int end) where T : IComparable<T>
		{
			// Validate the parameters
			if (seq == null || seq.Count <= 1)
			{
				throw new ArgumentException("Unable to produce permutations for lists with less than two values");
			}
			
			if (start < 0 || start >=  seq.Count)
			{
				throw new IndexOutOfRangeException("The start index is out of range");
			}
			
			if (end < 0 || end >= seq.Count)
			{
				throw new IndexOutOfRangeException("The end index is out of range");
			}
			
			if (end <= start)
			{
				throw new ArgumentException("The end index must be greater than the start index");
			}
			
			// Declare the j and m index positions and default to -1
			int j = -1;
			int m = -1;

			// Attempt to find the j index, this is the first index where it's value is less than the
			// one after it (i.e. seq[j] < seq[j+1])
			for (int index = (end - 1); index >= start; index--)
			{
				if (seq[index].CompareTo(seq[index + 1]) < 0)
				{
					j = index;
					break;
				}
			}

			// If no index was found then we are done
			if (j == -1)
			{
				return false;
			}

			// Find the m index, this is first index where it's value is greater than the value
			// at index j
			for (int index = end; index > j; index--)
			{
				if (seq[index].CompareTo(seq[j]) > 0)
				{
					m = index;
					break;
				}
			}

			// Swap the values at index j and m
			T holder = seq[j];
			seq[j] = seq[m];
			seq[m] = holder;

			// Sort all of the values after j in an ascending order
			seq = Sort<T>(seq, j + 1, end, SortOrder.Ascending);

			return true;
		}

		/// <summary>
		/// Produces the next lexicographical permutation of a sequence
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="seq">The sequence to produce the next permutation from</param>
		/// <param name="start">The starting index to produce the permutation from</param>
		/// <param name="end">The last index of the sequence to produce the permutation to</param>
		public static bool NextPermutation<T>(ref T[] seq, int start, int end) where T : IComparable<T>
		{
			List<T> seqList = new List<T>(seq);
			bool result = NextPermutation<T>(ref seqList, start, end);
			seq = seqList.ToArray();

			return result;
		}

		/// <summary>
		/// Calculates the number of possible permutations for a given sequence
		/// </summary>
		/// <param name="lengthOfSequence">The length of the sequence</param>
		public static int NumberOfPermutations(int lengthOfSequence)
		{
			return Factorial(lengthOfSequence);
		}
	}
}
